package com.zdb.datastructures.stack;

import java.util.Arrays;

public class Queue {

    private static int max = 8;

    private static int[] arr = new int[max];

    private static int cnt = 0;

    public static void main(String[] args) {

        System.out.println("---------");
        check(0);
        System.out.println("可行方案数：" + cnt);

    }

    /**
     * 尝试第n行放置皇后
     * @param n
     */
    private static void check(int n) {
        // 当max行时，说明max行都已经放置好了，返回
        if(n == max) {
            cnt ++;
            print();
            return;
        }

        // 从第一个位置开始放
        for (int i = 0; i < max; i++) {
            arr[n] =i;
            // 如果不冲突，进入下一行
            if(judge(n)) {
                check(n + 1);
            } else {
                // 冲突，放弃该位置，进入下一循环尝试
            }
        }

    }


    /**
     * 判断第n行放置的是否冲突，需要检查与前 n-1 行是否冲突
     * @param n 检查n行是否冲突
     * @return 冲突返回false,不冲突返回true
     */
    private static boolean judge(int n) {

        for (int i = 0; i < n; i++) {

            // 判断与i行是否在列、对角线是否冲突
            // 列冲突
            if(arr[i] == arr[n]) {
                return false;
            } 
            // 对角线，x,y两边等距
            else if(Math.abs(n-i) == Math.abs(arr[n] - arr[i])) {
                return false;
            }

        }
        return true;
    }

    private static void print() {
        System.out.println("成功方案：\t" +  Arrays.toString(arr));
    }
}
